/**
  * @file    :child_sibling_tree.hpp
  * @brief   :孩子兄弟表示法树模板
  * @author  :TMJ
  * @version :V1.0.0
  * @date    :2023-12-29
*/

#ifndef _TREE_CHILD_SIBLING_TREE_H_
#define _TREE_CHILD_SIBLING_TREE_H_

#include <iostream>
#include <queue>
#include <type_traits>


// 孩子兄弟表示树的结点定义
template<typename type>
struct ChildSiblingNode {

    // 构造函数
    ChildSiblingNode(type &data,
                     ChildSiblingNode<type> *firstChild = nullptr,
                     ChildSiblingNode<type> *nextSibling = nullptr)
        : _data(data), _firstChild(firstChild), _nextSibling(nextSibling) {}

    type _data;                                 // 数据域
    struct ChildSiblingNode<type> *_firstChild; // 第一个孩子指针
    struct ChildSiblingNode<type> *_nextSibling;// 下一个兄弟指针
};

// 孩子兄弟表示树的模板类定义
template<typename type>
class ChildSiblingTree {
private:
    ChildSiblingNode<type> *_root;// 树的根节点

public:
    // 无参构造函数
    ChildSiblingTree() : _root(nullptr) {}

    // 使用带有 “（）” 的字符串创建树
    void createTreeByPreorderStr(type *&str) {
        this->_createSubTreeByPreorderStr(this->_root, str);
    }

    // 判断是否为空树
    bool isEmpty() {
        return this->_root == nullptr;
    }

    // 获取结点数量
    int getNodeCount() {
        return this->_getNodeCountOfSubTree(this->_root);
    }

    // 获取树的高度
    int getHeight() {
        return this->_getHeightOfSubTree(this->_root);
    }

    // 获取根节点
    ChildSiblingNode<type> *getRoot() {
        return this->_root;
    }

    // 先序遍历
    void preorder(void (*visit)(ChildSiblingNode<type> *)) {
        this->_preorderSubTreeByRecursive(this->_root, visit);
    }

    // 后序遍历
    void postorder(void (*visit)(ChildSiblingNode<type> *)) {
        this->_postorderSubTreeByRecursive(this->_root, visit);
    }

    // 层序遍历
    void level(void (*visit)(ChildSiblingNode<type> *)) {
        this->_levelSubTree(this->_root, visit);
    }

    // 打印树
    void print() {
        this->_printSubTree(this->_root);
    }

private:
    // 子树删除（递归）
    void _deleteInSubTreeRecursive(ChildSiblingNode<type> *subRoot);

    // 先序遍历树
    void _preorderSubTreeByRecursive(ChildSiblingNode<type> *subRoot, void (*visit)(ChildSiblingNode<type> *));

    // 后序遍历树
    void _postorderSubTreeByRecursive(ChildSiblingNode<type> *subRoot, void (*visit)(ChildSiblingNode<type> *));

    // 层序遍历
    void _levelSubTree(ChildSiblingNode<type> *subRoot, void (*visit)(ChildSiblingNode<type> *));

    // 使用字符串创建子树
    void _createSubTreeByPreorderStr(ChildSiblingNode<type> *&subRoot, type *&str);

    // 获取子树结点数量
    int _getNodeCountOfSubTree(ChildSiblingNode<type> *subRoot);

    // 获取子树深度
    int _getHeightOfSubTree(ChildSiblingNode<type> *subRoot);

    // 打印子树
    void _printSubTree(ChildSiblingNode<type> *subRoot);
};

// 子树删除（递归）
template<typename type>
void ChildSiblingTree<type>::_deleteInSubTreeRecursive(ChildSiblingNode<type> *subRoot) {
    if (subRoot == nullptr) {
        return;
    }

    _deleteInSubTreeRecursive(subRoot->_firstChild);
    _deleteInSubTreeRecursive(subRoot->_nextSibling);

    delete subRoot;
}

// 先序遍历树
template<typename type>
void ChildSiblingTree<type>::_preorderSubTreeByRecursive(ChildSiblingNode<type> *subRoot,
                                                         void (*visit)(ChildSiblingNode<type> *)) {
    if (subRoot == nullptr) {
        return;
    }

    visit(subRoot);// 访问根节点

    _preorderSubTreeByRecursive(subRoot->_firstChild, visit); // 访问子节点
    _preorderSubTreeByRecursive(subRoot->_nextSibling, visit);// 访问兄弟结点
}

// 后序遍历树
template<typename type>
void ChildSiblingTree<type>::_postorderSubTreeByRecursive(ChildSiblingNode<type> *subRoot,
                                                          void (*visit)(ChildSiblingNode<type> *)) {
    if (subRoot == nullptr) {
        return;
    }

    _preorderSubTreeByRecursive(subRoot->_firstChild, visit);// 访问子节点

    visit(subRoot);// 访问根节点

    _preorderSubTreeByRecursive(subRoot->_nextSibling, visit);// 访问兄弟结点
}

// 层序遍历
template<typename type>
void ChildSiblingTree<type>::_levelSubTree(ChildSiblingNode<type> *subRoot,
                                           void (*visit)(ChildSiblingNode<type> *)) {
    if (_root == nullptr) {
        return;
    }

    std::queue<ChildSiblingNode<type> *> nodeQue;
    nodeQue.push(subRoot);

    while (!nodeQue.empty()) {
        ChildSiblingNode<type> *cur = nodeQue.front();
        nodeQue.pop();

        visit(cur);

        for (ChildSiblingNode<type> *node = cur->_firstChild; node != nullptr; node = node->_nextSibling) {
            nodeQue.push(node);
        }
    }
}

// 使用字符串创建子树
template<typename type>
void ChildSiblingTree<type>::_createSubTreeByPreorderStr(ChildSiblingNode<type> *&subRoot, type *&str) {
    // 空串处理
    if (*str == type('\0')) {
        return;
    }

    // 子树结束处理
    if (*str == type(')')) {
        str++;
        return;
    }

    while (*str == type('(')) {
        str++;
    }

    // 创建子树根节点
    type curData;
    if (std::is_same<type, int>::value) {
        curData = (type)(*str - '0');
    } else if (std::is_same<type, char>::value) {
        curData = *str;
    }

    str++;

    subRoot = new ChildSiblingNode<type>(curData);
    if (!subRoot) {
        throw std::bad_alloc();
    }

    _createSubTreeByPreorderStr(subRoot->_firstChild, str);
    _createSubTreeByPreorderStr(subRoot->_nextSibling, str);
}

// 获取子树结点数量
template<typename type>
int ChildSiblingTree<type>::_getNodeCountOfSubTree(ChildSiblingNode<type> *subRoot) {
    if (subRoot == nullptr) {
        return 0;
    }

    int nodeCount = 1;

    nodeCount += _getNodeCountOfSubTree(subRoot->_firstChild); // 计算孩子的结点数量
    nodeCount += _getNodeCountOfSubTree(subRoot->_nextSibling);// 计算兄弟的结点数量

    return nodeCount;
}

// 获取子树深度
template<typename type>
int ChildSiblingTree<type>::_getHeightOfSubTree(ChildSiblingNode<type> *subRoot) {
    // 空树处理
    if (subRoot == nullptr) {
        return 0;
    }

    int selfHeight = _getHeightOfSubTree(subRoot->_firstChild) + 1;
    int brotherHeight = _getHeightOfSubTree(subRoot->_nextSibling);
    int maxHeight = selfHeight > brotherHeight ? selfHeight : brotherHeight;

    return maxHeight;
}

// 打印子树
template<typename type>
void ChildSiblingTree<type>::_printSubTree(ChildSiblingNode<type> *subRoot) {
    // ---------- 1 空树处理 ----------

    if (subRoot == nullptr) {
        return;
    }

    // ---------- 2 打印'('和子树根结点 ----------

    std::cout << '(';
    std::cout << subRoot->_data;

    // ---------- 3 递归打印所有孩子结点的子树 ----------

    for (ChildSiblingNode<type> *cur = subRoot->_firstChild; cur != nullptr; cur = cur->_nextSibling) {
        _printSubTree(cur);
    }

    // ---------- 4 打印')' ----------

    std::cout << ')';
}

#endif// _TREE_CHILD_SIBLING_TREE_H_